Embedded systems are getting more complicated with more multiprocessors employed to solve complex problems. Solid-state drive (SSD) controllers have also been following this trend. Such environments typically have limited computer resources with S/W running on these processors competing for them. The limited computer resources that may be shared include main memory, cache memory, logical units (LUNs) of storage capacity such as may be provided by magnetic disk drives, solid state drives, and flash memory, and the files or records stored therein (e.g., a database), various types of input/output (I/O) ports or interfaces, and controllers or engines (e.g., direct memory access engine).
Allocation of global common resources in a multiple central processing unit (multi-CPU) environment is very challenging. Generally software solutions are employed that make use of mutual exclusion object (mutex) protections over resource pools to ensure that each resource pool is tracked and managed by only one central processing unit (CPU) at a time. In computer programming, a mutex is a program object that allows multiple program threads to share the same resource, such as file access, but not simultaneously. When a program is started, a mutex is created with a unique name. After this stage, any program instruction thread that needs to use the shared computer resource locks the mutex from being used by other instruction threads while it is using the computer resource. The mutex is set to unlock when the computer resource is no longer needed or the program routine is finished.
Unfortunately, tracking mutex availability of multiple computer resources available to multiple CPUs wastes valuable CPU bandwidth, typically measured in million instructions per second (MIPS). Further, resource allocation solutions struggle to ensure fairness in allocation of the same computer resource to multiple CPUs. For example, assume that CPU-X and CPU-Y (in that order) are trying to allocate for future use a computer resource that is currently not available. When the computer resource becomes available, it is challenging to ensure that CPU-X is not starved for the resource, that CPU-X gets access to the resource before CPU-Y.
Another aspect of the computer resource problem is resource allocation deadlocks. A resource allocation deadlock occurs when multiple CPUs need access to the same resource at the same time; the system cannot resolve the conflict; and the system becomes deadlocked (e.g., stalled or stuck) on use of the resource. Furthermore, if multiple types of computer resources are required for accomplishing a task, each type of computer resource (resource type) needs to be allocated individually. Accordingly, the complexity of resource allocation increases if the subsequent resource type is not available. Thus, there is a high potential of deadlocks if multiple resource allocation is not done in an atomic fashion.
For example, assume there are 3 different resource types in the system, R1, R2 and R3. Each resource type has only one resource each. CPU-X needs one of each of the resource types R1, R2, R3. CPU-Y needs one of each of resources R3 and R2. CPUs allocate resources as needed simultaneously as follows: (a) CPU-X is able to allocate one each of R1 and R2, but it failed to allocate one of R3 (it just happened to be taken by CPU-Y); (b) CPU-Y is able to allocate one of R3, but failed to allocate one of R2 (taken by CPU-X). This situation leads to a deadlock. CPU-X is holding R2 and waiting for R3. Whereas, CPU-Y is holding R3 and waiting for R2.
Conventional software solutions to resolve such resource allocation deadlocks leave a lot to be desired. In one solution, software running on all CPUs must ensure that different resource types are allocated in a fixed specific order (e.g., first R1, then R2, then R3, and so on). Any CPU requiring R3 and R2 must allocate R2 first and then R3. This solution is complex to manage in a multi-CPU environment requiring multiple resources.
In another solution, if a CPU requires multiple resource types, if it is successful in allocating a few resources but fails to allocate one, then the CPU should give back (e.g., release) all the resources allocated and try again later. This solution wastes lots of CPU MIPS to allocate and free resources every time the CPU fails to allocate one of the many resources needed. For example, imagine when each resource allocation requires taking a mutex. Additionally, this solution also adds to software complexity and size.
In yet another solution, software can be structured such that at any given time, only one global (commonly shared) resource allocation is required. Allocating multiple resource types at any given time is NOT permitted. Unfortunately, this solution adds a huge requirement on software design.
In sum, allocation of global common resources in a multiple central processor unit (multi-CPU) environment is very challenging. Conventional software solutions employed for such scenarios have run into many problems, such as deadlocks, software complexity, wastage of CPU bandwidth (e.g., MIPS), etc.